import math,operator

#todo:error process

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def is_prime(n):
    """
    check if a number is a prime
    """
##Implement Details:
##1 is not a prime.
##All primes except 2 are odd.
##All primes greater than 3 can be written in the form 6k+/-1.
##Any number n can have only one primefactor greater than n
    if n==1:
        return False
    elif n<4:
        return True
    elif n % 2 == 0:
        return False
    elif n < 9 :
        #we have already excluded 4,6,8
        return True
    elif n % 3 == 0:
        return False

    r = int(n**.5)
    f = 5
    while f <= r:
        #check 6*n -1
        if n % f == 0:
            return False
        #check 6*n + 1
        if n % (f+2) == 0:
            return False
        f+=6
    else:
        return True

def prime_factorization(n):
    """
    factorize a integer
    return a list of tuple (prime,power)
    """
    factors = []
    factor,power = 2,0
    while n%factor == 0:
        n/=factor
        power +=1
    if power:
        factors.append((factor,power))

    factor,power = 3,0
    maxFactor = n**.5
    while n > 1 and factor <= maxFactor:
        if n % factor == 0:
            power = 1
            n/=factor

            while n % factor == 0:
                n/= factor
                power+=1
            factors.append((factor,power))
        factor += 2

    return factors

def fraction(numerator,denominator=1):
    if isinstance(numerator,Fraction):
        return numerator
    elif isinstance(numerator,int):
        return Fraction(numerator,denominator)
    elif isinstance(numerator,long):
        return Fraction(numerator,denominator)
    elif isinstance(numerator,float):
        #todo parse the float to the fraction
        raise ValueError
    else:
        print type(numerator)
        raise ValueError("what type?")
        
    
        
#############seperate line################
class Fraction:

    
    def __init__(self,numerator,denominator=1):
        """
        denominator shoud always be positive.
        """
        if denominator == 0:
            raise ValueError("denominator can't be zero")
        if numerator < 0 and denominator < 0 :
            numerator,denominator = -numerator,-denominator
        elif numerator < 0 or denominator <0 :
            numerator,denominator = -abs(numerator),abs(denominator)

        reduction = gcd(numerator,denominator)
        self.numerator,self.denominator = numerator/reduction,denominator/reduction

    def __add__(self,other):
        """
        a/b + c/d = (ad + bc) / bd
        """
        other = fraction(other)
        return Fraction(self.numerator*other.denominator+other.numerator*self.denominator,
                        self.denominator*other.denominator)

    def __radd__(self,left):
        left = fraction(left)
        return Fraction(left.numerator*self.denominator+self.numerator*left.denominator,
                        left.denominator*self.denominator)

    def __sub__(self,other):
        """
        a/b - c/d = (ad - bc) / bd
        """
        other = fraction(other)
        return Fraction(self.numerator*other.denominator-other.numerator*self.denominator,
                        self.denominator*other.denominator)
    def __rsub__(self,left):
        left = fraction(left)
        return Fraction(left.numerator*self.denominator-self.numerator*left.denominator,
                        left.denominator*self.denominator)

    def __mul__(self,other):
        """
        a/b * c/d = (b*d)/(a*c)
        """
        other = fraction(other)
        return Fraction(self.numerator*other.numerator,self.denominator*other.denominator)

    def __rmul__(self,left):
        left = fraction(left)
        return Fraction(left.numerator*self.numerator,left.denominator*self.denominator)
        
    def __pow__(self,other,modulo):
        """
        (a/b)**k = (a**k)/(b**k)
        """
        return Fraction(self.numerator**other,self.denominator**other)
    
    def __div__(self,other):
        """
        (a/b) / (c/d) = (a*c)/(b*d)
        """
        other = fraction(other)
        return Fraction(self.numerator*other.denominator,other.numerator*self.denominator)

    def __rdiv__(self,left):
        left = fraction(left)
        return Fraction(left.numerator*self.denominator,self.numerator*left.denominator)
        
    def __neg__(self):
        """
        -(a/b) = -a / b
        """
        return Fraction(-self.numerator,self.denominator)

    def __int__(self):
        """
        int(a/b) = (a//b)
        """
        return self.numerator//self.denominator

    def __float__(self):
        """
        float(a/b) = float(a)/b
        """
        return float(self.numerator)/self.denominator
    
    def __invert__(self):
        """
        ~(a/b) = b/a
        """
        return Fraction(self.denominator,self.numerator)
    
    def __lt__(self,other):
        if not isinstance(other,self.__class__):
            return (float(self.numerator)/self.denominator) < other

        return ((self.numerator*other.denominator - other.numerator*other.denominator)<0)

    def __le__(self,other):
        if not isinstance(other,self.__class__):
            return (float(self.numerator)/self.denominator) <= other

        return ((self.numerator*other.denominator - other.numerator*other.denominator)<=0)

    def __eq__(self,other):
        if not isinstance(other,self.__class__):
            return (float(self.numerator)/self.denominator) == other

        return ((self.numerator*other.denominator - other.numerator*other.denominator)==0)

    def __ne__(self,other):
        if not isinstance(other,self.__class__):
            return (float(self.numerator)/self.denominator) != other

        return ((self.numerator*other.denominator - other.numerator*other.denominator)!=0)

    def __gt__(self,other):
        if not isinstance(other,self.__class__):
            return (float(self.numerator)/self.denominator) > other

        return ((self.numerator*other.denominator - other.numerator*other.denominator)>0)

    def __ge__(self,other):
        if not isinstance(other,self.__class__):
            return (float(self.numerator)/self.denominator) >= other

        return ((self.numerator*other.denominator - other.numerator*other.denominator)>=0)

    def __cmp__(self,other):
        if not isinstance(other,self.__class__):
            return (float(self.numerator)/self.denominator) - other

        return (self.numerator*other.denominator - other.numerator*other.denominator)

    def __nonzero__(self):
        return self.numerator!=0
    
    def __hash__(self):
        return (self.numerator*13+self.denominator)*29

    def __abs__(self):
        return Fraction(abs(self.numerator),abs(self.denominator))

    def __repr__(self):
##        return "Fraction(%d,%d)"%(self.numerator,self.denominator)
        return "%d/%d"%(self.numerator,self.denominator)


class ContinuedFraction:
    pass


